<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    939. Valid Permutations for DI Sequence
   </h1>
   <p>
    We are given
    <code>
     S
    </code>
    , a length
    <code>
     n
    </code>
    string of characters from the set
    <code>
     {'D', 'I'}
    </code>
    . (These letters stand for "decreasing" and "increasing".)
   </p>
   <p>
    A&nbsp;
    <em>
     valid permutation
    </em>
    &nbsp;is a permutation
    <code>
     P[0], P[1], ..., P[n]
    </code>
    of integers&nbsp;
    <code>
     {0, 1, ..., n}
    </code>
    , such that for all
    <code>
     i
    </code>
    :
   </p>
   <ul>
    <li>
     If
     <code>
      S[i] == 'D'
     </code>
     , then
     <code>
      P[i] &gt; P[i+1]
     </code>
     , and;
    </li>
    <li>
     If
     <code>
      S[i] == 'I'
     </code>
     , then
     <code>
      P[i] &lt; P[i+1]
     </code>
     .
    </li>
   </ul>
   <p>
    How many valid permutations are there?&nbsp; Since the answer may be large,
    <strong>
     return your answer modulo
     <code>
      10^9 + 7
     </code>
    </strong>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input: </strong><span id="example-input-1-1">"DID"</span>
<strong>Output: </strong><span id="example-output-1">5</span>
<strong>Explanation: </strong>
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= S.length &lt;= 200
     </code>
    </li>
    <li>
     <code>
      S
     </code>
     consists only of characters from the set
     <code>
      {'D', 'I'}
     </code>
     .
    </li>
   </ol>
   <div>
    <p>
     &nbsp;
    </p>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    939. DI 序列的有效排列
   </h1>
   <p>
    我们给出
    <code>
     S
    </code>
    ，一个源于&nbsp;
    <code>
     {'D', 'I'}
    </code>
    &nbsp;的长度为
    <code>
     n
    </code>
    &nbsp;的字符串 。（这些字母代表 &ldquo;减少&rdquo; 和 &ldquo;增加&rdquo;。）
    <br>
    <em>
     有效排列
    </em>
    &nbsp;是对整数
    <code>
     {0, 1, ..., n}
    </code>
    &nbsp;的一个排列&nbsp;
    <code>
     P[0], P[1], ..., P[n]
    </code>
    ，使得对所有的&nbsp;
    <code>
     i
    </code>
    ：
   </p>
   <ul>
    <li>
     如果
     <code>
      S[i] == 'D'
     </code>
     ，那么&nbsp;
     <code>
      P[i] &gt; P[i+1]
     </code>
     ，以及；
    </li>
    <li>
     如果
     <code>
      S[i] == 'I'
     </code>
     ，那么
     <code>
      P[i] &lt; P[i+1]
     </code>
     。
    </li>
   </ul>
   <p>
    有多少个有效排列？因为答案可能很大，所以请
    <strong>
     返回你的答案模
    </strong>
    <strong>
     <code>
      10^9 + 7
     </code>
    </strong>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例：
    </strong>
   </p>
   <pre><strong>输入：</strong>"DID"
<strong>输出：</strong>5
<strong>解释：</strong>
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= S.length &lt;= 200
     </code>
    </li>
    <li>
     <code>
      S
     </code>
     仅由集合
     <code>
      {'D', 'I'}
     </code>
     &nbsp;中的字符组成。
    </li>
   </ol>
   <p>
    &nbsp;
   </p>
  </div>
 </body>
</html>